package practice_2025_7_8;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /**
     * 丢失的数字
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int n = 0;
        int len = nums.length;
        for(int i = 0; i <= len; i++) {
            n ^= i;
        }
        for(int i = 0; i < len; i++) {
            n ^= nums[i];
        }
        return n;
    }

    /**
     * 只出现一次的数字
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < 32; i++) {
            int k = 0;
            for(int j = 0; j < nums.length; j++) {
                k += ((nums[j] >> i) & 1);
            }
            res |= ((k % 3) << i);
        }
        return res;
    }

    /**
     * 消失的两个数
     * @param nums
     * @return
     */
    // 总数: len + 2
    // 总数: len + 2
    public static int[] missingTwo(int[] nums) {
        int len = nums.length;
        // 1 - n
        int sum = 0;
        for(int i = 1; i <= len + 2; i++) {
            sum ^= i;
        }
        for(int i = 0; i < len; i++) {
            sum ^= nums[i];
        }
        // 最右侧的 1 -> 两个数不同的地方
        int k = sum & (-sum);
        //    System.out.println("sum: " + sum + " k:" + k);
        int num1 = 0;
        for(int i = 0; i < len; i++) {
            if ((k & nums[i]) != 0) {
                num1 ^= nums[i];
            }
        }
        for(int i = 0; i <= len + 2; i++) {
            if ((k & i ) != 0) {
                num1 ^= i;
            }
        }
        int num2 = (sum ^ num1);
        return new int[] {num1, num2};
    }

    /**
     * 两整数之和
     * @param a
     * @param b
     * @return
     */
    public int getSum(int a, int b) {
        int carray = (a & b) << 1;
        int sum = a ^ b;
        while(carray != 0) {
            int oldSum = sum;
            sum ^= carray;
            carray = (oldSum & carray) << 1;
        }
        return sum;
    }

    /**
     * 外观数列
     * @param n
     * @return
     */
    public static String countAndSay(int n) {
        // 递归出口
        if (n == 1) {
            return "1";
        }
        String str = countAndSay(n - 1);
        StringBuilder res = new StringBuilder();
        char num = str.charAt(0);
        int count = 0;
        for(int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == num) {
                count++;
            } else {
                res.append(count);
                res.append(num);
                count = 1;
                num = str.charAt(i);
            }
        }
        res.append(count);
        res.append(num);
        return res.toString();
    }

    /**
     * 数青蛙
     * @param croakOfFrogs
     * @return
     */
    public static int minNumberOfFrogs(String croakOfFrogs) {
        Map<Character, Integer> hash = new HashMap<>();
        hash.put('c', 0);
        hash.put('r', 1);
        hash.put('o', 2);
        hash.put('a', 3);
        hash.put('k', 4);
        int[] res = new int[5];
        for(int i = 0; i < croakOfFrogs.length(); i++) {
            char ch = croakOfFrogs.charAt(i);
            int index = hash.get(ch);
            int last = (index + res.length - 1) % res.length;
            if (res[last] != 0) {
                res[index]++;
                res[last]--;
            } else if (index == 0) {
                res[index]++;
            } else {
                return -1;
            }
        }
        for(int i = 0; i < res.length - 1; i++) {
            if (res[i] != 0) return -1;
        }
        return res[res.length - 1];
    }

    public static void main(String[] args) {
        missingTwo(new int[]{2});
        countAndSay(4);
        minNumberOfFrogs("croakcroak");
    }
}
